package com.emeraldparser.parse;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

import com.emeraldparser.grammar.Grammar;
import com.emeraldparser.grammar.Rule;
import com.emeraldparser.symbol.AlternationSymbolClass;
import com.emeraldparser.symbol.CharSequenceSymbolClass;
import com.emeraldparser.symbol.CharacterRangeSymbolClass;
import com.emeraldparser.symbol.CharacterSymbolClass;
import com.emeraldparser.symbol.ConcatenationSymbolClass;
import com.emeraldparser.symbol.EndOfInputSymbolClass;
import com.emeraldparser.symbol.NamedSymbolClass;
import com.emeraldparser.symbol.OptionalSymbolClass;
import com.emeraldparser.symbol.RepetitionSymbolClass;
import com.emeraldparser.symbol.StartOfInputSymbolClass;
import com.emeraldparser.symbol.Symbol;
import com.emeraldparser.symbol.SymbolClass;
import com.emeraldparser.symbol.SymbolClass.State;
import com.emeraldparser.symbol.SymbolClassScanner;
import com.emeraldparser.symbol.SymbolClasses;
import com.emeraldparser.util.Automaton;
import com.emeraldparser.util.Automatons;
import com.emeraldparser.util.Characters;
import com.emeraldparser.util.DepthFirstVisitor;
import com.emeraldparser.util.Graph;
import com.emeraldparser.util.Graph.Edge;
import com.emeraldparser.util.Path;
import com.google.common.base.Joiner;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
import com.google.common.collect.HashMultiset;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Multiset;
import com.google.common.collect.Sets;

public class ClassWriter {

	private final Grammar grammar;
	private final Automaton<ParseState, SymbolClass> automaton;
	private final BiMap<ParseState, Integer> stateNumbersByState = HashBiMap.create();
	private final Collection<Rule> rules;
	private final Map<SymbolClass.State, Rule> rulesBySymbolClassState = Maps.newHashMap();
	private final BiMap<SymbolClass, Integer> classNumbers = HashBiMap.create();
	private final Map<SymbolClass, String> symbolClassConstantNames = Maps.newHashMap();
	private final Map<Rule, Integer> ruleNumbers = Maps.newHashMap();
	private final Map<Rule, String> ruleConstantNames = Maps.newHashMap();

	public ClassWriter(Grammar grammar, Automaton<ParseState, SymbolClass> automaton, Collection<Rule> rules) {
		this.grammar = grammar;
		this.automaton = automaton;
		
		int nextStateNumber = 1;
		for (ParseState state : automaton.vertices()) {
			stateNumbersByState.put(state, nextStateNumber++);
		}
		
		int nextClassNumber = 1;
		Set<SymbolClass> symbolClasses = Sets.newHashSet();
		for (Graph.Edge<ParseState, SymbolClass> edge : automaton.edges()) {
			symbolClasses.add(edge.getLabel());
		}
		
		for (Rule rule : rules) {
			symbolClasses.add(rule.getLeftSymbolClass());
			symbolClasses.add(rule.getRightSymbolClass());
		}
		
		for (SymbolClass symbolClass : symbolClasses) {
			classNumbers.put(symbolClass, nextClassNumber);
			
			String constantName;
			try {
				constantName = computeConstantName(symbolClass);
			} catch (IllegalArgumentException e) {
				constantName = "SYMBOL_CLASS_" + nextClassNumber;
			}
			constantName = "SYMBOL_CLASS_" + nextClassNumber;
			symbolClassConstantNames.put(symbolClass, constantName);
			
			nextClassNumber++;
		}
		
		this.rules = rules;
		
		int nextRuleNumber = 1;
		
		for (Rule rule : rules) {
			
			int ruleNumber = nextRuleNumber++;
			String constantName = "rule" + ruleNumber;
			ruleNumbers.put(rule, ruleNumber);
			ruleConstantNames.put(rule, constantName);
			
			Automaton<SymbolClass.State, SymbolClass> leftAutomaton = rule.getLeftAutomaton();
			for (SymbolClass.State symbolClassState : leftAutomaton.vertices()) {
				rulesBySymbolClassState.put(symbolClassState, rule);
			}
			
			Automaton<SymbolClass.State, SymbolClass> rightAutomaton = rule.getRightAutomaton();
			for (SymbolClass.State symbolClassState : rightAutomaton.vertices()) {
				rulesBySymbolClassState.put(symbolClassState, rule);
			}
		}
	}

	private int stateNumber(ParseState state) {
		return stateNumbersByState.get(state);
	}

	private String constantName(Rule rule) {
		return ruleConstantNames.get(rule);
	}

	private int classNumber(SymbolClass symbolClass) {
		try {
			return classNumbers.get(symbolClass);
		} catch (NullPointerException e) {
			throw new IllegalArgumentException("Unknown symbol class: " + symbolClass, e);
		}
	}

	public void writeParserFile() throws IOException {
		Set<NamedSymbolClass> namedSymbolClasses = Sets.newHashSet();
		
		for (Graph.Edge<ParseState, SymbolClass> edge : automaton.edges()) {
			SymbolClass symbolClass = edge.getLabel();
			if (symbolClass instanceof NamedSymbolClass) {
				namedSymbolClasses.add((NamedSymbolClass) symbolClass);
			}
		}
		
		Writer writer = new BufferedWriter(new FileWriter(new File("src/adam/Parser.java")));
		try {
			appendLine(writer, "package adam;");
			appendLine(writer);
			
			appendLine(writer, "import static com.emeraldparser.symbol.SymbolClasses.*;");
			appendLine(writer);
			
			appendLine(writer, "import com.emeraldparser.parse.AbstractParser;");
			appendLine(writer, "import com.emeraldparser.parse.AbstractRule;");
			appendLine(writer, "import com.emeraldparser.parse.AbstractState;");
			//appendLine(writer, "import com.emeraldparser.parse.Rule;");
			//appendLine(writer, "import com.emeraldparser.parse.State;");
			//appendLine(writer, "import com.emeraldparser.parse.Symbol;");
			appendLine(writer, "import com.emeraldparser.symbol.Symbol;");
			appendLine(writer, "import com.emeraldparser.symbol.Symbols;");
			appendLine(writer, "import com.emeraldparser.symbol.SymbolClass;");
			appendLine(writer, "import com.google.common.collect.ImmutableList;");
			appendLine(writer, "import com.google.common.collect.ImmutableMap;");
			appendLine(writer, "import com.google.common.collect.ImmutableSet;");
			appendLine(writer);
			
			appendLine(writer, "import java.io.BufferedReader;");
			appendLine(writer, "import java.io.File;");
			appendLine(writer, "import java.io.FileReader;");
			appendLine(writer, "import java.io.IOException;");
			appendLine(writer, "import java.io.Reader;");
			appendLine(writer, "import java.util.Collection;");
			appendLine(writer, "import java.util.Iterator;");
			appendLine(writer, "import java.util.List;");
			appendLine(writer);
			/*
			appendLine(writer, "import java.util.ArrayDeque;");
			appendLine(writer, "import java.util.ArrayList;");
			appendLine(writer, "import java.util.Collection;");
			appendLine(writer, "import java.util.Collections;");
			appendLine(writer, "import java.util.Deque;");
			appendLine(writer, "import java.util.HashSet;");
			appendLine(writer, "import java.util.List;");
			appendLine(writer, "import java.util.Set;");
			appendLine(writer);
*/
			appendLine(writer, "public class Parser extends AbstractParser {");
			appendLine(writer);
			
			//appendLine(writer, "\tprivate static class SymbolClass {");
			//appendLine(writer, "\tprivate static final int CHARACTER = 1;");
			int constantValue = 2;
			for (NamedSymbolClass symbolClass : namedSymbolClasses) {
				//appendLine(writer, "\tprivate static final int " + computeConstantName(symbolClass) + " = " + constantValue + ";");
				constantValue++;
			}

			//appendLine(writer);
			
			int maxSymbolClassStringLength = -1;
			for (SymbolClass sc : classNumbers.keySet()) {
				maxSymbolClassStringLength = Math.max(maxSymbolClassStringLength, sc.toString().length());
			}
			
			Graph<SymbolClass, ?> dependencies = SymbolClasses.computeDependencies(classNumbers.keySet());
			System.out.println(dependencies);
			
			if (false) {
			while (!dependencies.vertices().isEmpty()) {
				boolean modified = false;
				
				for (Iterator<SymbolClass> i = dependencies.vertices().iterator(); i.hasNext();) {
					SymbolClass symbolClass = i.next();
					
					Collection<SymbolClass> predecessors = dependencies.predecessors(symbolClass);
					
					if (predecessors.isEmpty()) {
						appendLine(writer, "\tprivate final SymbolClass symbolClass" + classNumbers.get(symbolClass) + " = " + toJavaSourceCode(symbolClass) + ";");
						i.remove();
						modified = true;
					}
				}
				
				if (!dependencies.vertices().isEmpty() && !modified) {
					new DepthFirstVisitor<SymbolClass, Object>((Graph) dependencies) {
						
						@Override
						public void visit(SymbolClass symbolClass) {
							// TODO Auto-generated method stub
							if (isVisited(symbolClass)) {
								System.out.println(symbolClass + " has been visited!");
								System.out.println(getPath());
							}
							super.visit(symbolClass);
						}
						
					}.visit();
					
					throw new RuntimeException("Cyclic dependencies among symbol classes: " + dependencies);
				}
			}
			}
			
			for (Map.Entry<SymbolClass, Integer> entry : classNumbers.entrySet()) {
				/*ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
				ObjectOutputStream objectOutputStream = new ObjectOutputStream(byteArrayOutputStream);
				objectOutputStream.writeObject(entry.getKey());
				objectOutputStream.flush();
				
				String utf8 = new String(Base64.encodeBase64(byteArrayOutputStream.toByteArray()), "UTF-8");
				*/
				//appendLine(writer, "\tprivate final String thing" + entry.getValue() + " = \"" + utf8 + "\";");
				
				appendLine(writer, "\t/** " + entry.getKey()  + " */");
				appendLine(writer, "\tprivate final SymbolClass symbolClass" + entry.getValue() + " = " + toJavaSourceCode(entry.getKey()) + ";");
				
				String ss = entry.getKey().toString();
				String s = "\t/** " + ss;
				for (int i = ss.length(); i < maxSymbolClassStringLength; i++) {
					s += " ";
				}
				s += " */ private static final int " + constantName(entry.getKey()) + " = " + entry.getValue() + ";";
				//appendLine(writer, "\t/** " + entry.getKey() + " */ private static final int SYMBOL_CLASS_" + entry.getValue() + " = " + entry.getValue() + ";");
				//appendLine(writer, s);
				//appendLine(writer);
				constantValue++;
			}
			appendLine(writer);
			
			int maxRuleStringLength = -1;
			for (Rule rule : ruleNumbers.keySet()) {
				maxRuleStringLength = Math.max(maxRuleStringLength, rule.toString().length());
			}
			
			appendLine(writer, "\tprivate static abstract class Rule extends AbstractRule {");
			appendLine(writer);
			appendLine(writer, "\t\tprivate Collection<? extends State> startStates;");
			appendLine(writer);
			appendLine(writer, "\t\tprotected abstract Collection<? extends State> computeStartStates();");
			appendLine(writer);
			appendLine(writer, "\t\t@Override");
			appendLine(writer, "\t\tpublic Collection<? extends State> getStartStates() {");
			appendLine(writer, "\t\t\tif (startStates == null) {");
			appendLine(writer, "\t\t\t\tstartStates = computeStartStates();");
			appendLine(writer, "\t\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\t\treturn startStates;");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t}");
			appendLine(writer);
			
			for (Map.Entry<Rule, Integer> entry : ruleNumbers.entrySet()) {
				Rule rule = entry.getKey();
				String name = constantName(rule);
				
				String ss = rule.toString();
				String s = "\t/** " + ss;
				for (int i = ss.length(); i < maxRuleStringLength; i++) {
					s += " ";
				}
				s += " */ private static final int " + name + " = " + entry.getValue() + ";";
				appendLine(writer, "\t/** " + rule + " */");
				appendLine(writer, "\tprivate final Rule " + name + " = new Rule() {");
				appendLine(writer);

				appendLine(writer, "\t\t@Override");
				appendLine(writer, "\t\tpublic SymbolClass getLeftHandSide() {");
				appendLine(writer, "\t\t\treturn symbolClass" + classNumber(rule.getLeftSymbolClass()) + ";");
				appendLine(writer, "\t\t}");
				appendLine(writer);
				
				appendLine(writer, "\t\t@Override");
				appendLine(writer, "\t\tpublic SymbolClass getRightHandSide() {");
				appendLine(writer, "\t\t\treturn symbolClass" + classNumber(rule.getRightSymbolClass()) + ";");
				appendLine(writer, "\t\t}");
				appendLine(writer);
				
				appendLine(writer, "\t\t@Override");
				appendLine(writer, "\t\tprotected Collection<? extends State> computeStartStates() {");
				//appendLine(writer, "\t\t\tthrow new UnsupportedOperationException();");
				
				append(writer, "\t\t\treturn ImmutableSet.<State>builder()");
				
				Set<ParseState> seen = Sets.newHashSet();
				
				for (ParseState state : automaton.vertices()) {
					Automaton<SymbolClass.State, SymbolClass> rightAutomaton = rule.getRightAutomaton();
					
					Set<SymbolClass.State> acceptStates = Sets.newHashSet(rightAutomaton.getAcceptVertices());
					Set<SymbolClass.State> parseStates = Sets.newHashSet(state.downStates());
					
					if (!Sets.intersection(acceptStates, parseStates).isEmpty()) {
						//appendLine(writer, "\t\t\t// " + rule);
						//appendLine(writer, "\t\t\t//reductionPaths.addAll(pathsFrom());");
						
						Automaton<SymbolClass.State, SymbolClass> leftAutomaton = rule.getLeftAutomaton();
						
						Collection<Path<SymbolClass.State, SymbolClass>> paths = Automatons.findPaths(leftAutomaton);
						
						Multiset<Integer> pathLengths = HashMultiset.create();
						
						for (Path<SymbolClass.State, SymbolClass> path : paths) {
							pathLengths.add(path.size());
						}
						
						//appendLine(writer, "\t\t\t// Path lengths: " + pathLengths);
						//System.out.println(paths);
						
						for (ParseState candidate : automaton.vertices()) {
							Set<SymbolClass.State> candidateStates = Sets.newHashSet(candidate.downStates());
							if (!Sets.intersection(candidateStates, Sets.newHashSet(rightAutomaton.getStartVertices())).isEmpty()) {
								//appendLine(writer, "\t\t\treductionPaths.addAll(pathsFrom(state" + stateNumber(candidate) + "));");
								//appendLine(writer, "\t\t\tfor (List<Link> path : pathsFrom(state" + stateNumber(candidate) + ")) {");
								//appendLine(writer, "\t\t\t\treductions.add(new Reduction(" + constantName(rule) + ", path));");
								//appendLine(writer, "\t\t\t}");
								//appendLine(writer, "\t\t\tqueueReductionsFrom(" + constantName(rule) + ", state" + stateNumber(candidate) + "); // " + rule);
								if (seen.add(candidate)) {
									append(writer, ".add(state" + stateNumber(candidate) + ")");
								}
								
								if (paths.size() == 1) {
									//for (Graph.Edge<SymbolClass.State, SymbolClass> edge : Iterables.getOnlyElement(paths)) {
										//appendLine(writer, "\t\t\t// FIXME unreadSymbol(new Symbol<Object>(" + constantName(edge.getLabel()) + ", null)); // " + edge.getLabel());
									//}
								}
								//break;
							}
						}
					}
					
					// FIXME take care of up-states
					
				}
				
				appendLine(writer, ".build();");
				
				
				appendLine(writer, "\t\t}");
				appendLine(writer);
				
				Collection<Path<State, SymbolClass>> paths = Automatons.findPaths(rule.getLeftAutomaton());
				
				if (paths.size() == 1) {
					Path<State, SymbolClass> path = Iterables.getOnlyElement(paths);
					
					appendLine(writer, "\t\t@Override");
					appendLine(writer, "\t\tpublic List<? extends Symbol<?>> reduce(List<? extends Symbol<?>> rightHandSymbols) {");
					
					if (grammar.getTokenRules().contains(rule) && path.size() == 1) {
						// FIXME token rules may not necessarily have exactly one left-hand-side
						Edge<State, SymbolClass> edge = path.edges().iterator().next();
						appendLine(writer, "\t\t\treturn ImmutableList.of(Symbol.create(symbolClass" + classNumber(edge.getLabel()) + ", concatenateStrings(rightHandSymbols)));");
					} else {
						append(writer, "\t\t\treturn ImmutableList.<Symbol<?>>builder()");
						for (Edge<State, SymbolClass> edge : path.edges()) {
							//appendLine(writer, "\t\t\t\t.add(Symbol.create(symbolClass" + classNumber(edge.getLabel()) + ", rightHandSymbols))");
							append(writer, ".add(Symbol.create(symbolClass" + classNumber(edge.getLabel()) + ", rightHandSymbols))");
						}
						appendLine(writer, ".build();");
					}
					
					//appendLine(writer, "\t\t\t");
					appendLine(writer, "\t\t}");
					appendLine(writer);
				}

				
				appendLine(writer, "\t\t@Override");
				appendLine(writer, "\t\tpublic String toString() {");
				appendLine(writer, "\t\t\treturn \"" + Characters.escape(rule.toString()) + "\";");
				appendLine(writer, "\t\t}");
				appendLine(writer);
				
				appendLine(writer, "\t};");
				//appendLine(writer);
				appendLine(writer);
				//appendLine(writer, s);
			}
			
			//appendLine(writer, "\t}");
			appendLine(writer);
			
			ParseState startParseState = Iterables.getOnlyElement(automaton.getStartVertices());
			
			
			//appendLine(writer, "\tprivate final Reader reader;");
			//appendLine(writer, "\tprivate final Deque<Symbol<?>> bufferedSymbols = new ArrayDeque<Symbol<?>>();");
			//appendLine(writer, "\tprivate final Set<Node> topNodes = new HashSet<Node>();");
			//appendLine(writer);
			
			
			appendLine(writer, "\tpublic Parser(Iterator<? extends Symbol<?>> symbolIterator) {");
			appendLine(writer, "\t\tsuper(symbolIterator);");
			appendLine(writer, "\t}");
			appendLine(writer);
			
			appendLine(writer, "\tpublic static void main(String... args) throws IOException {");
			appendLine(writer, "\t\tFile file = new File(args[0]);");
			appendLine(writer);
			appendLine(writer, "\t\tReader reader = new FileReader(file);");
			appendLine(writer, "\t\ttry {");
			appendLine(writer, "\t\t\tBufferedReader bufferedReader = new BufferedReader(reader);");
			appendLine(writer, "\t\t\ttry {");
			appendLine(writer, "\t\t\t\tParser parser = new Parser(Symbols.iterator(bufferedReader));");
			appendLine(writer, "\t\t\t\tparser.parse();");
			appendLine(writer, "\t\t\t} finally {");
			appendLine(writer, "\t\t\t\tbufferedReader.close();");
			appendLine(writer, "\t\t\t}");
			appendLine(writer, "\t\t} finally {");
			appendLine(writer, "\t\t\treader.close();");
			appendLine(writer, "\t\t}");
			appendLine(writer, "\t}");
			appendLine(writer);
			
			/*
			appendLine(writer, "\tpublic void parse() throws IOException {");
			appendLine(writer, "\t\tState startState = state" + stateNumbersByState.get(startParseState) + ";");
			appendLine(writer, "\t\ttopNodes.add(new Node(startState));");
			appendLine(writer);
			appendLine(writer, "\t\tSymbol<?> symbol;");
			appendLine(writer, "\t\twhile ((symbol = readSymbol()) != null) {");
			appendLine(writer, "\t\t\tCollection<Reduction> reductions = new ArrayList<Reduction>(1);");
			appendLine(writer);
			appendLine(writer, "\t\t\tfor (Node node : topNodes) {");
			appendLine(writer, "\t\t\t\tnode.queueReductions(symbol, reductions);");
			appendLine(writer, "\t\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\t\tfor (Node node : clearTopNodes()) {");
			appendLine(writer, "\t\t\t\tnode.doShifts(symbol);");
			appendLine(writer, "\t\t\t}");
			appendLine(writer, "\t\t}");
			appendLine(writer, "\t}");
			appendLine(writer);
			*/
			
			appendLine(writer, "\t@Override");
			appendLine(writer, "\tprotected State getStartState() {");
			appendLine(writer, "\t\treturn state" + stateNumber(startParseState) + ";");
			appendLine(writer, "\t}");
			appendLine(writer);
			/*
			appendLine(writer, "\tprivate String concatenateStrings(Iterable<? extends Symbol<?>> symbols) {");
			appendLine(writer, "\t\tStringBuilder stringBuilder = new StringBuilder();");
			appendLine(writer, "\t\tfor (Symbol<?> symbol : symbols) {");
			appendLine(writer, "\t\t\tstringBuilder.append(String.valueOf(symbol.getSemanticValue()));");
			appendLine(writer, "\t\t}");
			appendLine(writer, "\t\treturn stringBuilder.toString();");
			appendLine(writer, "\t}");
			appendLine(writer);
			*/
			/*
			appendLine(writer, "\tprivate Collection<Node> clearTopNodes() {");
			appendLine(writer, "\t\tCollection<Node> oldTopNodes = new ArrayList<Node>(topNodes);");
			appendLine(writer, "\t\ttopNodes.clear();");
			appendLine(writer, "\t\treturn oldTopNodes;");
			appendLine(writer, "\t}");
			appendLine(writer);
			
			appendLine(writer, "\tprivate Symbol<?> readSymbol() throws IOException {");
			appendLine(writer, "\t\tif (bufferedSymbols.isEmpty()) {");
			appendLine(writer, "\t\t\treturn readCharacterSymbol();");
			appendLine(writer, "\t\t} else {");
			appendLine(writer, "\t\t\treturn bufferedSymbols.removeFirst();");
			appendLine(writer, "\t\t}");
			appendLine(writer, "\t}");
			appendLine(writer);
			
			appendLine(writer, "\tprivate Symbol<Character> readCharacterSymbol() throws IOException {");
			appendLine(writer, "\t\tint codePoint = reader.read();");
			appendLine(writer, "\t\tif (codePoint == -1) {");
			appendLine(writer, "\t\t\treturn null;");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			
			appendLine(writer, "\t\tchar character = (char) codePoint;");
			appendLine(writer, "\t\tswitch (character) {");
			for (SymbolClass symbolClass : symbolClassConstantNames.keySet()) {
				if (symbolClass instanceof CharacterSymbolClass) {
					CharacterSymbolClass characterSymbolClass = (CharacterSymbolClass) symbolClass;
					
					appendLine(writer, "\t\tcase '" + Characters.escape(characterSymbolClass.getCharacter()) + "': return new Symbol<Character>(" + constantName(characterSymbolClass) + ", character);");
				}
			}
			appendLine(writer, "\t\tdefault: throw new IllegalStateException(\"Illegal character: \" + character);");
			appendLine(writer, "\t\t}");
			
			//appendLine(writer, "\t\treturn new Symbol<Character>(CHARACTER, (char) codePoint);");
			appendLine(writer, "\t}");
			appendLine(writer);
			
			appendLine(writer, "\tprivate void unreadSymbol(Symbol<?> symbol) {");
			appendLine(writer, "\t\tbufferedSymbols.addFirst(symbol);");
			appendLine(writer, "\t}");
			appendLine(writer);
			
			appendLine(writer, "\tprivate void shiftState(Node currentNode, Symbol<?> symbol, State nextState) {");
			appendLine(writer, "\t\tNode rightSibling = null;");
			appendLine(writer);
			appendLine(writer, "\t\tSystem.out.println(\"Shifting state \" + nextState);");
			appendLine(writer);
			appendLine(writer, "\t\tfor (Node node : topNodes) {");
			appendLine(writer, "\t\t\tif (node.state == nextState) {");
			appendLine(writer, "\t\t\t\trightSibling = node;");
			appendLine(writer, "\t\t\t\tbreak;");
			appendLine(writer, "\t\t\t}");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\tif (rightSibling == null) {");
			appendLine(writer, "\t\t\trightSibling = new Node(nextState);");
			appendLine(writer, "\t\t\ttopNodes.add(rightSibling);");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\trightSibling.leftLinks.add(new Link(currentNode, symbol));");
			appendLine(writer, "\t}");
			appendLine(writer);
			

			appendLine(writer, "\tprivate Collection<List<Link>> pathsFrom(State startState) {");
			appendLine(writer, "\t\tCollection<List<Link>> paths = new ArrayList<List<Link>>(1);");
			appendLine(writer);
			appendLine(writer, "\t\tfor (Node node : topNodes) {");
			appendLine(writer, "\t\t\tpaths.addAll(pathsFrom(startState, node));");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\treturn paths;");
			appendLine(writer, "\t}");
			appendLine(writer);

			appendLine(writer, "\tprivate Collection<List<Link>> pathsFrom(State startState, Node currentNode) {");
			appendLine(writer, "\t\tCollection<List<Link>> paths = new ArrayList<List<Link>>(1);");
			appendLine(writer);
			appendLine(writer, "\t\tif (startState == currentNode.state) {");
			appendLine(writer, "\t\t\tpaths.add(Collections.<Link>emptyList());");
			appendLine(writer, "\t\t} else {");
			appendLine(writer, "\t\t\tfor (Link leftLink : currentNode.leftLinks) {");
			appendLine(writer, "\t\t\t\tfor (List<Link> leftPath : pathsFrom(startState, leftLink.leftSibling)) {");
			appendLine(writer, "\t\t\t\t\tList<Link> path = new ArrayList<Link>(leftPath.size() + 1);");
			appendLine(writer, "\t\t\t\t\tpath.addAll(leftPath);");
			appendLine(writer, "\t\t\t\t\tpath.add(leftLink);");
			appendLine(writer, "\t\t\t\t\tpaths.add(path);");
			appendLine(writer, "\t\t\t\t}");
			appendLine(writer, "\t\t\t}");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\treturn paths;");
			appendLine(writer, "\t}");
			appendLine(writer);
			*/
			/*
			appendLine(writer, "\tprivate static class Symbol<T> {");
			appendLine(writer);
			appendLine(writer, "\t\tfinal int symbolClass;");
			appendLine(writer, "\t\tfinal T semanticValue;");
			appendLine(writer);
			appendLine(writer, "\t\tSymbol(int symbolClass, T semanticValue) {");
			appendLine(writer, "\t\t\tthis.symbolClass = symbolClass;");
			appendLine(writer, "\t\t\tthis.semanticValue = semanticValue;");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t}");
			appendLine(writer);
			
			appendLine(writer, "\tprivate static class Node {");
			appendLine(writer);
			appendLine(writer, "\t\tfinal State state;");
			appendLine(writer, "\t\tfinal List<Link> leftLinks;");
			appendLine(writer);
			appendLine(writer, "\t\tNode(State state) {");
			appendLine(writer, "\t\t\tthis.state = state;");
			appendLine(writer, "\t\t\tthis.leftLinks = new ArrayList<Link>(1);");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\tprivate void queueReductions(Symbol<?> symbol, Collection<? super Reduction> reductions) {");
			appendLine(writer, "\t\t\tstate.queueReductions(this, symbol, reductions);");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\tprivate void doShifts(Symbol<?> symbol) {");
			appendLine(writer, "\t\t\tstate.doShifts(this, symbol);");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t}");
			appendLine(writer);
			
			appendLine(writer, "\tprivate static class Link {");
			appendLine(writer);
			appendLine(writer, "\t\tfinal Node leftSibling;");
			appendLine(writer, "\t\tfinal Symbol<?> symbol;");
			appendLine(writer);
			appendLine(writer, "\t\tLink(Node leftSibling, Symbol<?> symbol) {");
			appendLine(writer, "\t\t\tthis.leftSibling = leftSibling;");
			appendLine(writer, "\t\t\tthis.symbol = symbol;");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t}");
			appendLine(writer);
			
			appendLine(writer, "\tprivate static class Reduction {");
			appendLine(writer);
			appendLine(writer, "\t\tfinal int rule;");
			appendLine(writer, "\t\tfinal List<Link> rightHandPath;");
			appendLine(writer);
			appendLine(writer, "\t\tReduction(int rule, List<Link> rightHandPath) {");
			appendLine(writer, "\t\t\tthis.rule = rule;");
			appendLine(writer, "\t\t\tthis.rightHandPath = rightHandPath;");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t}");
			appendLine(writer);
			*/
			//appendLine(writer, "\tprivate abstract class State {");
			//appendLine(writer, "\tprivate enum State implements AbstractParser.State {");
			//appendLine(writer);
			
			List<ParseState> stateList = Lists.newArrayList(automaton.vertices());
			
			appendLine(writer, "\tprivate abstract class State extends AbstractState {");
			appendLine(writer);
			appendLine(writer, "\t\tprivate ImmutableMap<SymbolClass, State> nextStates;");
			appendLine(writer);
			appendLine(writer, "\t\tprotected ImmutableMap<SymbolClass, State> computeNextStates() {");
			appendLine(writer, "\t\t\treturn ImmutableMap.of();");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\tprotected ImmutableMap<SymbolClass, State> getNextStates() {");
			appendLine(writer, "\t\t\tif (nextStates == null) {");
			appendLine(writer, "\t\t\t\tnextStates = computeNextStates();");
			appendLine(writer, "\t\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\t\treturn nextStates;");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\t@Override");
			appendLine(writer, "\t\tpublic void queueReductions(Symbol<?> symbol) {");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\t@Override");
			appendLine(writer, "\t\tpublic void doShifts(Symbol<?> symbol) {");
			appendLine(writer, "\t\t\tState nextState = getNextStates().get(symbol.getSymbolClass());");
			appendLine(writer, "\t\t\tif (nextState != null) {");
			appendLine(writer, "\t\t\t\tshiftState(symbol, nextState);");
			appendLine(writer, "\t\t\t}");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t\t@Override");
			appendLine(writer, "\t\tpublic State nextState(Symbol<?> symbol) {");
			appendLine(writer, "\t\t\tState nextState = getNextStates().get(symbol.getSymbolClass());");
			appendLine(writer, "\t\t\tif (nextState != null) {");
			appendLine(writer, "\t\t\t\treturn nextState;");
			appendLine(writer, "\t\t\t} else {");
			appendLine(writer, "\t\t\t\tthrow new RuntimeException();");
			appendLine(writer, "\t\t\t}");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			appendLine(writer, "\t}");
			appendLine(writer);
			
			for (ListIterator<ParseState> i = stateList.listIterator(); i.hasNext();) {
				ParseState state = i.next();
				int stateNumber = stateNumber(state);
				
				Set<Rule> rules = Sets.newHashSet();
				
				for (SymbolClass.State symbolClassState : state.downStates()) {
					rules.add(rulesBySymbolClassState.get(symbolClassState));
				}

				for (SymbolClass.State symbolClassState : state.upStates()) {
					rules.add(rulesBySymbolClassState.get(symbolClassState));
				}
				
				//appendLine(writer, "\t\t/**");
				//for (Rule rule : rules) {
					//appendLine(writer, "\t * " + rule.toString(state.downStates(), state.upStates()));
				//}
				//appendLine(writer, "\t\t */");
				//appendLine(writer, "\t\tSTATE_" + stateNumber + " {");
				//appendLine(writer);
				
				appendLine(writer, "\t/**");
				if (!state.downStates().isEmpty()) {
					appendLine(writer, "\t * Down States:");
					for (SymbolClass.State downState : state.downStates()) {
						appendLine(writer, "\t *   " + downState);
					}
				}
				if (!state.upStates().isEmpty()) {
					appendLine(writer, "\t * Up States:");
					for (SymbolClass.State upState : state.upStates()) {
						appendLine(writer, "\t *   " + upState);
					}
				}
				appendLine(writer, "\t */");
				
				appendLine(writer, "\tprivate final State state" + stateNumber + " = new State() {");
				appendLine(writer);
				
				Collection<? extends SymbolClass> outbound = automaton.outboundEdgeLabels(state);
				
				if (!outbound.isEmpty()) {
					appendLine(writer, "\t\tprotected ImmutableMap<SymbolClass, State> computeNextStates() {");
					appendLine(writer, "\t\t\treturn ImmutableMap.<SymbolClass, State>builder()");
					
					for (SymbolClass symbolClass : outbound) {
						appendLine(writer, "\t\t\t\t.put(symbolClass" + classNumbers.get(symbolClass) + ", state" + stateNumber(Iterables.getOnlyElement(automaton.successors(state, symbolClass))) + ") // " + symbolClass);
					}
					
					appendLine(writer, "\t\t\t\t.build();");
					appendLine(writer, "\t\t}");
					appendLine(writer);
				}
				
				boolean hasReductions = false;

				for (Rule rule : rules) {
					Automaton<SymbolClass.State, SymbolClass> rightAutomaton = rule.getRightAutomaton();
					
					Set<SymbolClass.State> acceptStates = Sets.newHashSet(rightAutomaton.getAcceptVertices());
					Set<SymbolClass.State> parseStates = Sets.newHashSet(state.downStates());
					
					if (!Sets.intersection(acceptStates, parseStates).isEmpty()) {
						//appendLine(writer, "\t\t\t// " + rule);
						hasReductions = true;
						break;
					}
					
					// FIXME take care of up-states
					
				}
				
				
				if (hasReductions) {
					appendLine(writer, "\t\t@Override");
					appendLine(writer, "\t\tpublic void queueReductions(Symbol<?> symbol) {");
					
					for (Rule rule : rules) {
						Automaton<SymbolClass.State, SymbolClass> rightAutomaton = rule.getRightAutomaton();
						
						Set<SymbolClass.State> acceptStates = Sets.newHashSet(rightAutomaton.getAcceptVertices());
						Set<SymbolClass.State> parseStates = Sets.newHashSet(state.downStates());
						
						if (!Sets.intersection(acceptStates, parseStates).isEmpty()) {
							//appendLine(writer, "\t\t\t// " + rule);
							//appendLine(writer, "\t\t\t//reductionPaths.addAll(pathsFrom());");
							
							Automaton<SymbolClass.State, SymbolClass> leftAutomaton = rule.getLeftAutomaton();
							
							Collection<Path<SymbolClass.State, SymbolClass>> paths = Automatons.findPaths(leftAutomaton);
							
							Multiset<Integer> pathLengths = HashMultiset.create();
							
							for (Path<SymbolClass.State, SymbolClass> path : paths) {
								pathLengths.add(path.size());
							}
							
							//appendLine(writer, "\t\t\t// Path lengths: " + pathLengths);
							//System.out.println(paths);
							
							for (ParseState candidate : automaton.vertices()) {
								Set<SymbolClass.State> candidateStates = Sets.newHashSet(candidate.downStates());
								if (!Sets.intersection(candidateStates, Sets.newHashSet(rightAutomaton.getStartVertices())).isEmpty()) {
									//appendLine(writer, "\t\t\treductionPaths.addAll(pathsFrom(state" + stateNumber(candidate) + "));");
									//appendLine(writer, "\t\t\tfor (List<Link> path : pathsFrom(state" + stateNumber(candidate) + ")) {");
									//appendLine(writer, "\t\t\t\treductions.add(new Reduction(" + constantName(rule) + ", path));");
									//appendLine(writer, "\t\t\t}");
									//appendLine(writer, "\t\t\tqueueReductionsFrom(" + constantName(rule) + ", state" + stateNumber(candidate) + "); // " + rule);
									//if (paths.size() == 1) {
									//	for (Graph.Edge<SymbolClass.State, SymbolClass> edge : Iterables.getOnlyElement(paths)) {
											//appendLine(writer, "\t\t\t// FIXME unreadSymbol(new Symbol<Object>(" + constantName(edge.getLabel()) + ", null)); // " + edge.getLabel());
									//	}
									//}
									appendLine(writer, "\t\t\tParser.this.queueReductions(" + constantName(rule) + "); // " + rule);
									break;
								}
							}
						}
						
						// FIXME take care of up-states
						
					}
					
					appendLine(writer, "\t\t}");
					appendLine(writer);
				}
				

				boolean hasShifts = false;
				
				Set<CharacterSymbolClass> literals = Sets.newHashSet();
				Set<NamedSymbolClass> names = Sets.newHashSet();
				
				//appendLine(writer, "\t\t\tswitch (character) {");
				for (SymbolClass symbolClass : automaton.outboundEdgeLabels(state)) {
					if (symbolClass instanceof CharacterSymbolClass) {
						literals.add((CharacterSymbolClass) symbolClass);
						//appendLine(writer, "\t\t\tcase '" + Characters.escape(((CharacterSymbolClass) symbolClass).character()) + "': shiftState(state" + stateNumbersByState.get(Iterables.getOnlyElement(automaton.successors(state, symbolClass))) + "); break;");
						//appendLine(writer, "\t\t\t\tbreak;");
						//appendLine(writer);
						hasShifts = true;
					} else if (symbolClass instanceof NamedSymbolClass) {
						names.add((NamedSymbolClass) symbolClass);
						hasShifts = true;
					}
				}
				//appendLine(writer, "\t\t\t}");
				appendLine(writer, "\t\t@Override");
				appendLine(writer, "\t\tpublic String toString() {");
				//appendLine(writer, "\t\t\treturn \"" + state.toString().replaceAll("\"", "\\\\\"").replaceAll("\n", "\\n") + "\";");
				appendLine(writer, "\t\t\treturn \"State" + stateNumber + "\";");
				appendLine(writer, "\t\t}");
				appendLine(writer);
				
				
				if (false && hasShifts) {
					appendLine(writer, "\t\t@Override");
					appendLine(writer, "\t\tpublic void doShifts(Symbol<?> symbol) {");
					appendLine(writer, "\t\t\tshiftState(symbol, nextStates.get(symbol.getSymbolClass()));");
					/*
					appendLine(writer, "\t\t\t/* FIXME");
					appendLine(writer, "\t\t\tswitch (symbol.symbolClass) {");
					for (SymbolClass sc : automaton.outboundEdgeLabels(state)) {
						ParseState dest = Iterables.getOnlyElement(automaton.successors(state, sc));
						appendLine(writer, "\t\t\tcase " + constantName(sc) + ": // " + sc);
						appendLine(writer, "\t\t\t\tshiftState(symbol, state" + stateNumber(dest) + "); break;");
					}
					appendLine(writer, "\t\t\t}");
					appendLine(writer, "\t\t\t*");
					*/
					/*
					appendLine(writer, "\t\t\tswitch (symbol.symbolClass) {");
					
					for (NamedSymbolClass name : names) {
						appendLine(writer, "\t\t\tcase " + computeConstantName(name) + ": shiftState(node, symbol, state" + stateNumber(Iterables.getOnlyElement(automaton.successors(state, name))) + "); break;");
					}
					
					if (!literals.isEmpty()) {
						appendLine(writer, "\t\t\tcase CHARACTER:");
						//appendLine(writer, "\t\t\t\tchar character = (Character) symbol.semanticValue;");
						appendLine(writer, "\t\t\t\tswitch ( (Character) symbol.semanticValue ) {");
						
						for (CharacterSymbolClass literal : literals) {
							appendLine(writer, "\t\t\t\tcase '" + Characters.escape(literal.character()) + "': shiftState(node, symbol, state" + stateNumbersByState.get(Iterables.getOnlyElement(automaton.successors(state, literal))) + "); break;");
						}
						
						//appendLine(writer, "\t\t\t\tdefault: super.doShifts(node, symbol); break;");
						appendLine(writer, "\t\t\t\t}");
						appendLine(writer, "\t\t\t\tbreak;");
					}
					
					//appendLine(writer, "\t\t\tdefault: super.doShifts(node, symbol); break;");
					appendLine(writer, "\t\t\t}");
					*/
					
					

					appendLine(writer, "\t\t}");
					appendLine(writer);
					
					appendLine(writer, "\t\t@Override");
					appendLine(writer, "\t\tpublic State nextState(Symbol<?> symbol) {");
					appendLine(writer, "\t\t\treturn nextStates.get(symbol.getSymbolClass());");
					appendLine(writer, "\t\t}");
					appendLine(writer);
/*
				appendLine(writer, "\t\t@Override");
				appendLine(writer, "\t\tpublic String toString() {");
				appendLine(writer, "\t\t\treturn \"State" + stateNumber + "\";");
				appendLine(writer, "\t\t}");
				appendLine(writer);
	*/
				}
				
				if (i.hasNext()) {
					appendLine(writer, "\t};");
				} else {
					appendLine(writer, "\t};");
				}
				appendLine(writer);
			}
/*
			appendLine(writer, "\t\tpublic void queueReductions(Node node, Symbol<?> symbol, Collection<? super Reduction> reductions) {");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			
			appendLine(writer, "\t\tpublic void doShifts(Node node, Symbol<?> symbol) {");
			//appendLine(writer, "\t\t\tthrow new IllegalStateException();");
			appendLine(writer, "\t\t}");
			appendLine(writer);
			
			appendLine(writer, "\t}");
			appendLine(writer);
*/			
			appendLine(writer, "}");
		} finally {
			writer.close();
		}
	}

	private String toJavaSourceCode(SymbolClass symbolClass) {
		return new SymbolClassScanner<Void, String>() {

			@Override
			public String visitAlternationSymbolClass(AlternationSymbolClass alternationSymbolClass, Void input) {
				return "any(" + Joiner.on(", ").join(scan(alternationSymbolClass.getAlternatedSymbolClasses(), input)) + ")";
			}

			@Override
			public String visitCharacterRangeSymbolClass(CharacterRangeSymbolClass characterRangeSymbolClass, Void input) {
				return "range('" + Characters.escape(characterRangeSymbolClass.getLowerBound()) + "', '" + Characters.escape(characterRangeSymbolClass.getUpperBound()) + "')";
			}

			@Override
			public String visitCharacterSymbolClass(CharacterSymbolClass characterSymbolClass, Void input) {
				return "literal('" + Characters.escape(characterSymbolClass.getCharacter()) + "')";
			}

			@Override
			public String visitCharSequenceSymbolClass(CharSequenceSymbolClass charSequenceSymbolClass, Void input) {
				return "literal(\"" + Characters.escape(charSequenceSymbolClass.getCharSequence()) + "\")";
			}

			@Override
			public String visitConcatenationSymbolClass(ConcatenationSymbolClass concatenationSymbolClass, Void input) {
				return "concat(" + Joiner.on(", ").join(scan(concatenationSymbolClass.getConcatenatedSymbolClasses(), input)) + ")";
			}

			@Override
			public String visitNamedSymbolClass(NamedSymbolClass namedSymbolClass, Void input) {
				return "named(\"" + namedSymbolClass.getName() + "\")";
			}

			@Override
			public String visitOptionalSymbolClass(OptionalSymbolClass optionalSymbolClass, Void input) {
				return "optional(" + scan(optionalSymbolClass.getOptionalSymbolClass(), input) + ")";
			}

			@Override
			public String visitRepetitionSymbolClass(RepetitionSymbolClass repetitionSymbolClass, Void input) {
				return "repeated(" + scan(repetitionSymbolClass.getRepeatedSymbolClass(), input) + ")";
			}

			@Override
			public String visitEndOfInputSymbolClass(EndOfInputSymbolClass endOfInputSymbolClass, Void input) {
				return "endOfInput()";
			}

			@Override
			public String visitStartOfInputSymbolClass(StartOfInputSymbolClass startOfInputSymbolClass, Void input) {
				return "startOfInput()";
			}
			
		}.scan(symbolClass, null);
	}

	private String constantName(SymbolClass symbolClass) {
		return symbolClassConstantNames.get(symbolClass);
	}

	private String computeConstantName(SymbolClass symbolClass) {
		if (symbolClass instanceof NamedSymbolClass) {
			return ((NamedSymbolClass) symbolClass).getName().toUpperCase().replaceAll("\\\\", "SLASH_");
		} else if (symbolClass instanceof RepetitionSymbolClass) {
			return "REPEATED_" + computeConstantName(((RepetitionSymbolClass) symbolClass).getRepeatedSymbolClass());
		} else if (symbolClass instanceof AlternationSymbolClass) {
			String s = "";
			
			String d = "";
			for (SymbolClass sc : ((AlternationSymbolClass) symbolClass).getAlternatedSymbolClasses()) {
				s += d + computeConstantName(sc);
				d = "_OR_";
			}
			
			return s;
		} else if (symbolClass instanceof CharacterSymbolClass) {
			CharacterSymbolClass characterSymbolClass = (CharacterSymbolClass) symbolClass;
			
			char ch = characterSymbolClass.getCharacter();
			
			if (('a' <= ch && ch <= 'z')
			 || ('A' <= ch && ch <= 'Z')
			 || ('0' <= ch && ch <= '9')) {
				return ch + "_LITERAL";
			}
		}
		
		throw new IllegalArgumentException();
	}

	private void appendLine(Appendable appendable) throws IOException {
		appendable.append("\r\n");
	}

	private void appendLine(Appendable appendable, Object text) throws IOException {
		appendable.append(String.valueOf(text)).append("\r\n");
	}

	private void append(Appendable appendable, Object text) throws IOException {
		appendable.append(String.valueOf(text));
	}

}
